\chapter {Compilatori e linguaggi funzionali}


\section {Introduzione alla compilazione}
\subsection {Il compilatore}

I linguaggi di programmazione sono una notazione con cui le persone
indicano cosa fare all'elaboratore, e ogni programma \`e scritto in un 
qualche linguaggio di programmazione. Ma, prima che un programma possa essere
eseguito, deve essere tradotto in una forma tale da essere eseguibile da un elaboratore.
Il sistema software che effettua questa traduzione \`e chiamato \emph{compilatore}. 

Il compilatore \`e quindi un programma che legge un programma scritto nel linguaggio \emph{sorgente}
e lo traduce in un programma ``equivalente'' scritto nel linguaggio \emph{target}, come mostrato
in Figura~\ref{fig:comp}~\cite{compiler}.

\begin{figure}[h]
\caption{\label{fig:comp} Un Compilatore}
\begin{center}
\makebox{
\includegraphics{./comp}
}
\end{center}
\end{figure}

Se il programma target \`e un programma eseguibile, pu\`o essere direttamente eseguito dall'utente.

Un \emph{interprete} \`e un altro tipo di elaboratore di linguaggi. 
Invece che produrre un programma target, come risultato della traduzione, l'interprete
esegue direttamente le operazioni specificate nel programma sorgente con gli input
specificati dall'utente, come mostrato in Figura~\ref{fig:int}.

\begin{figure}[h]
\caption{\label{fig:int} Un Interprete}
\begin{center}
\makebox{
\includegraphics{./int}
}
\end{center}
\end{figure}

\subsection{Architettura di un compilatore}

Fino ad ora abbiamo trattato il compilatore come una scatola unica che
mappa un programma sorgente in un programma target semanticamente equivalente.
Se apriamo questa scatola vediamo che questo processo \`e divisibile
in due parti: \emph{analisi} e \emph{sintesi}.

La fase di \emph{analisi} si occupa di spezzare il programma sorgente nelle sue
parti costituenti e imporre ad esse una struttura per creare una
rappresentazione intermedia del programma sorgente.

La fase di \emph{sintesi} si occupa di costruire il programma 
target a partire dalla rappresentazione intermedia.

Esaminando meglio il processo di compilazione, vediamo che esso
opera in una sequenza di fasi, che trasformano una rappresentazione
del programma sorgente in un'altra, come mostrato in Figura~
\ref{fig:phases}.

\begin{figure}[h]
\caption{\label{fig:phases} Fasi di un compilatore}
\begin{center}
\makebox{
\includegraphics{./phases}
}
\end{center}
\end{figure}

La separazione in fasi \`e solo concettuale. 
In pratica, diverse fasi possono essere raggruppate insieme, 
e la rappresentazione intermedia fra esse non deve essere 
necessariamente costruita.

\paragraph{Analizzatore Lessicale}
La prima fase di un compilatore \`e chiamata 
\emph{analisi lessicale} o \emph{scanning}.
L'analizzatore lessicale legge lo stream di caratteri del programma
sorgente e li raggruppa in sequenze chiamate \emph{lessemi}, con
i quali produce in output i \emph{token}. Consideriamo ad esempio, il
seguente frammento di codice:


\begin{ScriptMath}
position := initial + rate * 60
\end{ScriptMath}


I caratteri di questo assegnamento possono essere raggruppati nei
seguenti lessemi e mappati nei corrispondenti token, che verranno
passati all'analizzatore sintattico.

\begin{enumerate}
\item \verb+position+ \`e un lessema che sar\`a mappato con un
token di tipo identificatore, con nome position.
\item \verb+:=+ \`e un lessema che sar\`a mappato come se stesso.
\item \verb+initial+ \`e un lessema che sar\`a mappato con un
token di tipo identificatore, con nome initial.
\item \verb-+- \`e un lessema che sar\`a mappato come se stesso.
\item \verb+rate+ \`e un lessema che sar\`a mappato con un
token di tipo identificatore, con nome rate.
\item \verb-*- \`e un lessema che sar\`a mappato come se stesso.
\item \verb-60- \`e un lessema che sar\`a mappato con un token di
tipo numero con valore 60.
\end{enumerate}

\paragraph{Analizzatore Sintattico}
La seconda fase del compilatore \`e l'\emph{analisi sintattica} o
\emph{parsing}.
In questa fase i token vengono raggruppati in frasi grammaticali
per creare una rappresentazione intermedia simile ad un albero
che rappresenti la struttura grammaticale dello stream di token.  

Una tipica rappresentazione \`e l'\emph{albero sintattico}, nel
quale ogni nodo interno rappresenta un'operazione e i figli del
nodo rappresentano gli argomenti dell'operazione, come mostrato
in Figura~\ref{fig:ast}. 

\begin{figure}[!hbt]
\caption{\label{fig:ast} Albero sintattico}
\begin{center}
\makebox{
\includegraphics{./ast}
}
\end{center}
\end{figure}

\paragraph{Analizzatore Semantico}
L'analizzatore semantico usa l'albero sintattico prodotto nella 
fase precedente per controllare la consistenza semantica
del programma sorgente rispetto alla definizione del linguaggio.

Una parte importante dell'analisi semantica \`e il \emph{controllo dei tipi},
in cui il compilatore controlla 
che ogni operatore abbia gli operandi del tipo richiesto.

\paragraph{Generatore di Codice Intermedio}
Dopo l'analisi sintattica e semantica del programma sorgente,
molti compilatori generano una rappresentazione intermedia
di basso livello del codice stesso, che pu\`o essere pensato
come un programma per una macchina astratta.
Questa rappresentazione intermedia deve avere due importanti
propriet\`a: deve essere facile da produrre e deve essere facile
tradurlo nel linguaggio macchina. Un possibile codice intermedio
per l'albero sintattico mostrato in Figura~\ref{fig:ast} \`e 
il seguente:

\begin{ScriptMath}
t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
\end{ScriptMath}

In questo esempio si vede la necessit\`a del compilatore di 
generare nomi temporanei per memorizzare i risultati intermedi
dell'elaborazione.

\paragraph{Ottimizzatore del codice}
Questa fase tenta di migliorare il codice intermedio 
precedentemente generato, ma non esiste un codice ottimale.
Generalmente per migliorare si intende rendere pi\`u veloce, ma
si potrebbe anche volere un codice pi\`u compatto o un codice che
abbia un minore consumo di potenza.

A volte questa fase pu\`o essere fusa con la fase di generazione
del codice visto che certe ottimizzazioni sono possibili solo
conoscendo il linguaggio target.

\paragraph{Generatore di Codice}
Questa fase prende in input la rappresentazione intermedia del
programma sorgente e produce in output un programma scritto
nel linguaggio target.
Se il linguaggio target \`e il codice macchina, registri e 
locazioni di memoria sono scelti per ogni variabile usata
dal programma. Poi le istruzioni intermedie sono tradotte
in una sequenza di istruzioni macchina che effettuano lo
stesso compito.
 
\subsection {Perch\'e usare un codice intermedio}

L'uso di un codice intermedio \`e importante in quanto 
aggiunge modularit\`a al compilatore. Senza un codice intermedio
avendo $n$ linguaggi di programmazione e $m$ architetture si dovrebbero
generare $m~x~n$ compilatori, come mostrato in Figura~\ref{fig:mxn}.

\begin{figure}[h]
\caption{\label{fig:mxn} M x N compilatori}
\begin{center}
\makebox{
\includegraphics{./mxn}
}
\end{center}
\end{figure}

Invece usando un codice intermedio, basta generare $m~+~n$ compilatori, come
mostrato in Figura~\ref{fig:m+n}. Inoltre, se venisse sviluppata una nuova
architettura, basterebbe generare il compilatore dal codice intermedio
a questa nuova architettura, per poter eseguire programmi che condividono 
quel codice intermedio su questa architettura.

\begin{figure}[h]
\caption{\label{fig:m+n} M + N compilatori}
\begin{center}
\makebox{
\includegraphics{./m+n}
}
\end{center}
\end{figure}

\section {Linguaggi funzionali e loro compilazione}

\subsection {Introduzione ai linguaggi funzionali}

I linguaggi di programmazione funzionali sono una classe
di linguaggi progettati per rispecchiare il modo in cui le 
persone pensano in maniera matematica, piuttosto che pensare
alla macchina sottostante.
Essi sono basati sul \emph{lambda calcolo}, un
semplice modello di computazione, e permettono di ragionare in maniera
formale sui programmi. Il lambda calcolo~\cite{lambda} \`e un modello 
di computazione progettato da Alonzo Church
negli anni '30 che fornisce un modo molto formale di descrivere
la valutazione di funzioni. 
Esso pu\`o essere considerato il primo linguaggio di 
programmazione funzionale, anche se non fu progettato per essere eseguito 
su una macchina.
I linguaggi funzionali oggi pi\`u conosciuti, tutti derivati pi\`u o meno 
direttamente
dal lambda calcolo, sono ML~\cite{ml}, Haskell~\cite{haskell} e Lisp~\cite{lisp}.
Un programma funzionale quindi, assume la forma di una serie di valutazioni di
funzioni matematiche, a differenza dei linguaggi imperativi in cui un programma
consiste in una serie di comandi che modificano lo stato della memoria.
Nei paragrafi seguenti vedremo le caratteristiche di un linguaggio funzionale
tramite degli esempi.\footnote{Gli esempi presentati sono scritti in OCaml
\cite{ocaml}.}

\subsubsection{Assenza di Variabili}
A differenza dei linguaggi imperativi, nei quali le variabili rappresentano
celle di memoria che possono essere modificate tramite un assegnamento, i 
linguaggi funzionali vedono l'uso dell'operatore $=$ come un'espressione di
un'equazione. Consideriamo il seguente frammento di programma:
\lstset{language=[Objective]Caml,
      print=true,
      basicstyle=\small\ttfamily,
      mathescape=true}
%
\begin{ScriptMath}
let a = 1 
let f x = x + a
f 2
\end{ScriptMath} 
%
La prima istruzione introduce il nome \lstinline!a! e lo lega al numero 1. 
Poi viene
definita una funzione che somma il valore in ingresso ad \lstinline!a!,
 e la funzione
viene applicata al numero 2, ottenendo come risultato il numero 3.
Ridefinendo il nome \lstinline!a!, legandolo al numero 3, 
e richiamando la funzione
precedentemente definita col valore \lstinline!2!, si ottiene di nuovo come risultato
il numero 3 e non 5, come si potrebbe pensare.
%
\begin{ScriptMath}
let a = 3 
f 2\end{ScriptMath} 
%
Questo dimostra che il nome \lstinline!a! non \`e legato ad una locazione di memoria
modificabile, ma \`e solo un nome definito nel programma.
Visto che al momento della definizione della funzione \lstinline!f! il nome
\lstinline!a! era legato al valore \lstinline!1!,
 questo rester\`a tale per sempre; ridefinendo
il nome \lstinline!a! la funzione non cambier\`a il comportamento.

\subsubsection {Funzioni di prima classe }
I linguaggi funzionali trattano le funzioni come valori di prima classe,
cio\`e permettono di memorizzare le funzioni in strutture dati, 
passarle come parametro ad una funzione o essere il valore
di ritorno di un'altra funzione. Consideriamo il seguente esempio: 
%
\begin{ScriptMath}
(fun x $\to$ 1 + x, 5)
\end{ScriptMath} 
%
In quest'esempio viene creata una coppia
in cui il primo elemento \`e una funzione e il secondo un numero intero.
Ci\`o \`e possibile in quanto le funzioni vengono trattate come ogni altro
valore e possono quindi anche essere memorizzate all'interno di una coppia.
Inoltre \`e possibile definire \emph{funzioni anonime} in qualsiasi punto
del codice, proprio a testimonianza del fatto che le funzioni sono trattate come
qualsiasi altro valore.

\subsubsection{Funzioni di ordine superiore}
Una funzione di ordine superiore \`e una funzione che accetta come parametro 
un'altra funzione o che restituisce come risultato una funzione.
In un linguaggio funzionale scrivere funzioni di ordine superiore \`e
naturale come scrivere funzione di primo ordine, visto che le funzioni sono 
valori. Vediamo ora un esempio:
%
\begin{ScriptMath}
let compose = fun f $\to$ fun g $\to$ fun x $\to$ f (g x)
\end{ScriptMath} 
\lstset{language=[Objective]Caml,
      print=true,
      basicstyle=\small\ttfamily,
      mathescape=true}
Questo esempio implementa la composizione funzionale di due funzioni; infatti
\lstinline!compose! prende in input una funzione, 
che a sua volta prende in input una 
funzione che prende in input un valore e applica la prima funzione
al risultato dell'applicazione della seconda funzione al valore.
Qua si vede chiaramente il passaggio di una funzione come parametro.
Se le funzioni \lstinline!f! e \lstinline!g! hanno un solo argomento, 
il risultato \`e un valore semplice,
mentre se la funzioni hanno pi\`u argomenti il risultato della funzione \`e una
nuova funzione.

Con questo esempio si nota anche che le funzioni multi-argomento non devono
essere native, visto che possono essere implementate tramite una sequenza di 
funzioni a un argomento, come visto sopra.


\subsubsection {Applicazione parziale}
\lstset{language=[Objective]Caml,
      print=true,
      basicstyle=\small\ttfamily,
      mathescape=true}
L'applicazione parziale di una funzione \`e l'applicazione di una funzione
ad una parte dei suoi argomenti. Questo tecnica permette di 
\emph{specializzare} una funzione. Supponendo di avere un predicato
\lstinline!even! che stabilisce se un numero \`e pari, e una funzione
\lstinline!not! che nega un predicato, consideriamo il seguente esempio:
%
\begin{ScriptMath}
(compose not) even
\end{ScriptMath} 
%
In questo esempio la funzione \lstinline!compose! viene applicata parzialmente
alla funzione \lstinline!not!, e il risultato viene poi applicato alla funzione
\lstinline!even!. L'applicazione parziale crea quindi una nuova funzione il cui
scopo \`e negare il risultato della valutazione del predicato.
In questo caso la funzione risultante sar\`a la funzione \lstinline!odd!, che 
stabilisce se un numero \`e dispari.

\subsubsection {Ricorsione}
Nei linguaggi funzionali non esiste l'iterazione visto che non esiste il 
concetto di variabile.
Infatti \`e impossibile implementare un ciclo iterativo che dipenda da una condizione 
che \`e per forza immodificabile.
Per questo la ricorsione assume un ruolo fondamentale. \`E inoltre dimostrabile che l'iterazione \`e
equivalente ad uno speciale tipo di ricorsione chiamata \emph{tail ricorsione}
\cite{tail}. Consideriamo ora il
seguente esempio, in cui lo stesso algoritmo viene implementato sia in maniera iterativa
che in maniera ricorsiva:\\
%
\lstset{language=[Objective]Caml,
      print=true,
      basicstyle=\small\ttfamily,
      mathescape=true}
\makebox[\textwidth]{
\begin{tabular}{lc@{\qquad}l}
& & \\
\lstinline!int fact(int n)\{! & &\lstinline!
let rec fact n =!\\
\quad \lstinline!int f = 1;! & &  \lstinline!if (n = 0) then 1! \\
\quad \lstinline!while (n > 1)\{! & &
\lstinline!else (n * fact (n - 1))! \\
\qquad\lstinline!f = f * n;!& & \\
\qquad \lstinline!n--;!& & \\
\quad \lstinline!\}!& &  \\
\lstinline!return (f);!& &  \\
\lstinline!\}!& &  \\
& &  \\
\end{tabular}
}
%
Entrambi gli algoritmi calcolano il fattoriale di un numero.
Il primo \`e scritto in maniera iterativa mentre il secondo \`e
scritto in maniera ricorsiva. Si nota subito la 
compattezza del codice ricorsivo rispetto a quello iterativo
e l'analogia della ricorsione
al concetto di induzione matematica.



\subsection {Compilazione dei linguaggi funzionali}
  
Come abbiamo visto un programma scritto in un linguaggio funzionale
assume la forma di una serie di valutazioni di funzioni matematiche.
Come \`e facile immaginarsi quindi \`e di cruciale importanza il modo
in cui vengono compilate le funzioni, tenendo conto delle  
caratteristiche viste in precedenza.

Una caratteristica dei linguaggi funzionali \`e l'assenza
di variabili intese come locazioni di memoria modificabili.
\`E possibile per\`o effettuare il \emph{binding} di un nome ad un
espressione e usare successivamente questo nome, come mostrato in questo
esempio:
%
\begin{ScriptMath}
let a = 1 
let f x = x + a
\end{ScriptMath} 
%
\lstset{language=[Objective]Caml,
      print=true,
      basicstyle=\small\ttfamily,
      mathescape=true}
Andando quindi a compilare la funzione \lstinline!f! \`e necessario ricordarsi 
il valore
di ogni variabile libera\footnote{Una variabile \`e libera se non \`e n\'e
un parametro della funzione n\'e una variabile locale alla funzione.} presente 
nell'ambiente in cui \lstinline!f! 
\`e definita; in
questo caso l'unica variabile libera \`e \lstinline!a!.
Per risolvere questo problema, \`e necessario l'uso delle \emph{chiusure}.

Una \emph{chiusura} \`e un'astrazione che combina una funzione con le variabili
libere presenti nell'ambiente in cui la funzione \`e definita.
Le variabili libere dell'ambiente rimangono accessibili per tutta la durata 
di vita della chiusura e pertanto persistono nel corso di invocazioni
successive della chiusura.
Il risultato di una chiusura \`e quindi un termine in cui non esistono 
pi\`u variabili libere.
Inoltre le chiusure devono poter essere passate come argomenti di una funzione.
Questo ci \`e molto utile per la compilazione di funzioni di ordine superiore e
per il fatto che le funzioni sono valori di prima classe.
Infatti per definizione, una funzione di ordine superiore \`e una funzione che
pu\`o accettare come parametro un'altra funzione.
Quindi se tutte le funzioni sono compilate con le chiusure, la compilazione
di funzioni di ordine superiore \`e semplice come la compilazione di ogni
altra funzione.

Vediamo ora in che modo \`e possibile implementare una chiusura. Come abbiamo
visto una chiusura \`e formata da dati e funzioni che operano su di essi e 
questo accoppiamento ci ha fatto venire l'idea di implementare una chiusura
tramite una classe di un linguaggio a oggetti. Le classi infatti sono:
\begin{quotation} 
``uno strumento per costruire strutture dati che contengono non
solo dati ma anche il codice per gestirli''~\cite{wikipedia}.
\end{quotation}
A causa di questa analogia abbiamo deciso di scegliere un linguaggio a oggetti
come linguaggio intermedio del nostro compilatore.

\section {Struttura della tesi}
Nel capitolo 2 mostreremo un semplice linguaggio funzionale ({\flang})
da noi definito e la sua compilazione in un altrettanto semplice
linguaggio a oggetti ({\olang}). La semplicit\`a dei linguaggi \`e tale
in quanto si vuol concentrare l'attenzione sulla bont\`a della scelta di un
linguaggio a oggetti come target della compilazione di un linguaggio
funzionale.

Nel capitolo 3 verr\`a mostrata un'estensione del linguaggio {\flang}, chiamato
{\cflang}, che offre al programmatore una sintassi pi\`u ricca, con cui fare
esempi concreti e la compilazione di questo linguaggio in un'estensione del
linguaggio {\olang} chiamato {\colang}.
Inoltre verr\`a mostrata la compilazione del linguaggio {\colang} nel linguaggio
Java.

Nel capitolo 4 si mostreranno le analogie
fra le caratteristiche fondamentali della programmazione a oggetti
e la compilazione di un linguaggio funzionale e si illustreranno i possibili
sviluppi futuri di questo lavoro.  

